package com.study.algorithm.datastruct.tree.impl;

import com.study.algorithm.datastruct.tree.AVlTreeOperate;
import com.study.algorithm.datastruct.tree.model.AVLTree;
import com.study.algorithm.datastruct.tree.model.BinaryTree;

import java.util.List;
import java.util.Queue;
import java.util.Stack;
import java.util.concurrent.LinkedBlockingQueue;


/**
 * 平衡二叉树操作
 * 构建平衡二叉树
 * 给平衡二叉树插入新节点
 */
public class AVlTreeOperateImpl extends TreeBaseOperate implements AVlTreeOperate {

    public static volatile AVlTreeOperate instance;

    public static AVlTreeOperate getInstance() {

        if (instance == null) {
            synchronized (AVlTreeOperateImpl.class) {
                if (instance == null) {
                    instance = new AVlTreeOperateImpl();
                }
            }
        }
        return instance;
    }


    @Override
    public boolean isBalanceBinaryTree(BinaryTree binaryTree) {
        int notbalance = -1;
        //同一节点，可能会扫描多次
//        return isBalance(binaryTree);
        //使用递归方式，同一节点只会扫描一次
        return isBalanceforOptimization(binaryTree) != notbalance;
    }

    @Override
    public AVLTree buildBalanceBinaryTreeTroughWeight(List<Integer> weights) {
        if (weights == null || weights.size() == 0) {
            return null;
        }
        int size = weights.size();
        AVLTree tree = new AVLTree();
        tree.setWeight(weights.get(0));

        for (int index = 1; index < size; index++) {
            int insertWeight = weights.get(index);
            tree = insertAVLTreeNodeThroughWeight(tree, insertWeight);
        }
        return tree;
    }

    @Override
    public AVLTree insertAVLTreeNodeThroughWeight(AVLTree rootNode, int weight) {
        NotBalanceNodeDetail notBalanceNodeDetail = new NotBalanceNodeDetail();
        notBalanceNodeDetail.init();
        addNodeThroughWeight(rootNode, weight);
        boolean isnotBalance = findNotBalanceNode(rootNode, notBalanceNodeDetail) == -1;
        if (!isnotBalance) {
            return rootNode;
        }
        AVLTree fatherNode = notBalanceNodeDetail.getFatherNode();
        AVLTree notBalanceNode = notBalanceNodeDetail.getNotBanlanceNode();
        boolean isNotBalanceForRootNode = fatherNode == null && rootNode == notBalanceNode;
        AVLTree rotateRootNode = adjustNotBalanceNode(notBalanceNode, weight, fatherNode);
        if (isNotBalanceForRootNode) {
            rootNode = rotateRootNode;
            return rootNode;
        }

        return rootNode;
    }

    @Override
    public AVLTree removeAVLTreeNodeThroughWeight(AVLTree rootNode, int weight) {
//todo:removeAVLTreeNode

        return null;
    }


    private AVLTree adjustNotBalanceNode(AVLTree notBalanceNode, int insertData, AVLTree fatherNode) {
        String rotateStyle = getRotateStyleThroughWeight(notBalanceNode, insertData);
        AVLTree rotateRootNode = rotateNotBalanceNode(rotateStyle, notBalanceNode);
        if (fatherNode == null) {
            return rotateRootNode;
        }
        //修正被旋转节点的父节点地址引用
        if (fatherNode.getRightChildNode() == notBalanceNode) {
            fatherNode.setRightChildNode(rotateRootNode);
        }
        if (fatherNode.getLeftChildNode() == notBalanceNode) {
            fatherNode.setLeftChildNode(rotateRootNode);
        }
        return rotateRootNode;
    }

    private AVLTree rotateNotBalanceNode(String rotateStyle, AVLTree notBalanceNode) {
        switch (rotateStyle) {
            case "RR":
                return RRRotate(notBalanceNode);
            case "RL":
                return RLRotate(notBalanceNode);
            case "LL":
                return LLRotate(notBalanceNode);
            case "LR":
                return LRRotate(notBalanceNode);
//            default:
//                throw new IllegalArgumentException("旋转类型参数错误");

        }
        return null;
    }

    private String getRotateStyleThroughWeight(AVLTree notBalanceNode, int insertNodeWeight) {
        boolean islChildInsert = notBalanceNode.getWeight() > insertNodeWeight;
        if (!islChildInsert) {
            AVLTree rChildNode = notBalanceNode.getRightChildNode();
            boolean isRR = rChildNode.getWeight() > insertNodeWeight;
            return isRR ? "RL" : "RR";
        }
        AVLTree lChildNode = notBalanceNode.getLeftChildNode();
        boolean isLL = lChildNode.getWeight() > insertNodeWeight;
        return isLL ? "LL" : "LR";
    }


    /**
     * 通过整数值（仿照权重值构建）添加新节点，
     * 节点位置定义，按照左小（包含等于）右大的原则
     *
     * @param rootNode
     * @param insertWeight 新添加节点的权重（可以理解为权重）
     */
    private void addNodeThroughWeight(AVLTree rootNode, int insertWeight) {
        if (rootNode == null) {
            rootNode = new AVLTree();
            rootNode.setWeight(insertWeight);
            return;
        }

        AVLTree fatherNode = rootNode;
        while (true) {
            boolean isBiggerThanInsert = fatherNode.getWeight() > insertWeight;
            AVLTree temp = isBiggerThanInsert ?
                    fatherNode.getLeftChildNode() : fatherNode.getRightChildNode();
            if (temp != null) {
                fatherNode = temp;
                continue;
            }
            temp = new AVLTree();
            temp.setWeight(insertWeight);
            if (isBiggerThanInsert) {
                fatherNode.setLeftChildNode(temp);

            } else {
                fatherNode.setRightChildNode(temp);
            }
            break;

        }
    }


    /**
     * @return 如果找到不平衡点就返回-1,找不到返回的是当前节点的深度（用来判断父节点是否平衡）
     */
    private int findNotBalanceNode(AVLTree rootTree, NotBalanceNodeDetail detail) {
        int deep = 0;
        int notBalance = -1;
        int rightChildDeep = 0;
        int leftChildDeep = 0;
        if (rootTree == null) {
            return deep;
        }
        deep += 1;
        //递归查找左右节点
        if (rootTree.hasLeftChildNode()) {
            leftChildDeep = findNotBalanceNode(rootTree.getLeftChildNode(), detail);
        }
        if (leftChildDeep != -1 && rootTree.hasRightChildNode()) {
            rightChildDeep = findNotBalanceNode(rootTree.getRightChildNode(), detail);
        }
        //如果找到不平衡点，直接返回
        if (leftChildDeep == -1 || rightChildDeep == -1) {
            if (!detail.isHasUpdatedFather()) {
                detail.setFatherNode(rootTree);
            }
            return notBalance;
        }
        //判断当前节点是否为不平衡点，并记录
        if (Math.abs(leftChildDeep - rightChildDeep) > 1) {
            detail.setNotBanlanceNode(rootTree);
            return notBalance;
        }
        deep += leftChildDeep > rightChildDeep ? leftChildDeep : rightChildDeep;
        return deep;


    }

    /**
     * LL旋转
     * 根据规律发现：只需要将不平衡节点左子节点向右旋转即可
     * 旋转点：旋转节点为不平节点的子节点
     * 不平衡点 ：A ，不平衡子节点：B ，导致不平的点（新插入的节点) :C
     * 何时需要该旋转：
     * 第一步确定：B节点是A的左子节点
     * 第二步确定：C是B的左子树上的节点时
     *
     * @return 返回旋转后的根节点
     */
    private AVLTree LLRotate(AVLTree notBalanceNode) {

        AVLTree lchildNode = notBalanceNode.getLeftChildNode();
        //旋转
        notBalanceNode.setLeftChildNode(lchildNode.getRightChildNode());
        lchildNode.setRightChildNode(notBalanceNode);
        return lchildNode;

    }

    /**
     * RR旋转
     * 根据规律发现：只需要将不平衡节点右子节点向左旋转即可
     * 旋转点：旋转节点为不平节点的子节点
     * 不平衡点 ：A ，不平衡子节点：B ，导致不平的点（新插入的节点) :C
     * 何时需要该旋转：
     * 第一步确定：B节点是A的右子节点
     * 第二步确定：C是B的右子树上的节点时
     * <p>
     * 注意事项：
     * 1）当不平衡节点为根节点时，需要将根节点重新定义为旋转后的根节点（原不平衡节点的右子节点）
     * 2）当不平衡节点不是根节点时，需要将不平衡节点的父节点的子节点重新定义
     *
     * @return 返回旋转后的根节点
     */
    private AVLTree RRRotate(AVLTree notBalanceNode) {
        AVLTree rchildNode = notBalanceNode.getRightChildNode();
        //旋转
        notBalanceNode.setRightChildNode(rchildNode.getLeftChildNode());
        rchildNode.setLeftChildNode(notBalanceNode);
        return rchildNode;
    }


    /**
     * LR旋转
     * * 不平衡点 ：A ，不平衡子节点：B ，B节点的右子节点：C，导致不平的点（新插入的节点) :D
     * 根据规律发现：旋转步骤
     * 第一步：先将节点C向左旋转，第二步：再将节点B向右旋转
     * 旋转点： B，C
     * 何时需要该旋转：
     * 第一步确定：B节点是A的左子节点
     * 第二步确定：D在C节点的子节点或者子树节点上
     *
     * @return 返回旋转后的根节点
     */
    private AVLTree LRRotate(AVLTree notBalanceNode) {
        AVLTree lChildNode = notBalanceNode.getLeftChildNode();
        AVLTree lrChildNode = lChildNode.getRightChildNode();
        // 第一步：将节点C向左旋转，
        lChildNode.setRightChildNode(lrChildNode.getLeftChildNode());
        lrChildNode.setLeftChildNode(lChildNode);
        //第二步：将节点B向右旋转
        notBalanceNode.setLeftChildNode(lrChildNode.getRightChildNode());
        lrChildNode.setRightChildNode(notBalanceNode);

        return lrChildNode;

    }

    /**
     * RL旋转
     * * 不平衡点 ：A ，不平衡子节点：B ，B节点的左子节点：C，导致不平的点（新插入的节点) :D
     * 根据规律发现：旋转步骤
     * 第一步：先将节点C向左旋转，第二步：再将节点B向右旋转
     * 旋转点： B，C
     * 何时需要该旋转：
     * 第一步确定：B节点是A的右子节点
     * 第二步确定：D在C节点的子节点或者子树节点上
     *
     * @return 返回旋转后的根节点
     */
    private AVLTree RLRotate(AVLTree notBalanceNode) {
        AVLTree rChildNode = notBalanceNode.getRightChildNode();
        AVLTree rlChildNode = rChildNode.getLeftChildNode();
        // 第一步：将节点C向左旋转，
        rChildNode.setLeftChildNode(rlChildNode.getRightChildNode());
        rlChildNode.setRightChildNode(rChildNode);
        //第二步：将节点B向右旋转
        notBalanceNode.setRightChildNode(rlChildNode.getLeftChildNode());
        rlChildNode.setLeftChildNode(notBalanceNode);

        return rlChildNode;

    }


    /**
     * 判断二叉树是否为平衡树，
     * 发现不平衡点即返回-1
     * 目前在不借助辅助字段的话，只想到该递归方式，
     * 如果你有其他方式，请不吝指教、补全
     *
     * @param binaryTree
     * @return
     */
    private int isBalanceforOptimization(BinaryTree binaryTree) {
        return getDeepForRootNodeOrJudgeBalance(binaryTree, true);
    }


    /**
     * 判断二叉树是否为平衡树，
     * 发现不平衡点即返回false
     *
     * @param binaryTree
     * @return
     */
    private boolean isBalance(BinaryTree binaryTree) {
        Stack<BinaryTree> treeStack =
                getBinaryTreeNodeStackThroughLevelTravel(binaryTree);
        //全栈扫描的方式（通过节点底部往上查找不平衡点）
        //未优化，底层节点的深度会重复扫描
        while (!treeStack.isEmpty()) {
            BinaryTree binaryTreeNode = treeStack.pop();
            if (binaryTreeNode == null) {
                continue;
            }
            int leftDeep = getDeepForBinaryTreeNode(binaryTreeNode.getLeftChildNode());
            int rightDeep = getDeepForBinaryTreeNode(binaryTreeNode.getRightChildNode());

            if (Math.abs(leftDeep - rightDeep) > 1) {
                return false;
            }
        }


        return true;
    }

    private Stack<BinaryTree> getBinaryTreeNodeStackThroughLevelTravel(BinaryTree binaryTree) {
        Stack<BinaryTree> resultStack = new Stack<>();
        Queue<BinaryTree> tempQueue = new LinkedBlockingQueue<>();
        if (binaryTree == null) {
            return resultStack;
        }
        resultStack.push(binaryTree);
        tempQueue.add(binaryTree);
        while (!tempQueue.isEmpty()) {
            BinaryTree binaryTreeNode = tempQueue.poll();
            if (binaryTreeNode == null) {
                continue;
            }
            tempQueue.add(binaryTreeNode);
            resultStack.push(binaryTreeNode);
        }
        return resultStack;
    }

    private int getDeepForBinaryTreeNode(BinaryTree binaryTree) {
        return getDeepForRootNodeOrJudgeBalance(binaryTree, false);
    }

    /**
     * 记录寻找不平衡点的辅助类
     * fatherNode 不平衡点的父节点
     * notBanlanceNode 不平衡节点
     * boolean hasUpdatedFather 是否已经更新父节点（防止父父节点重复更新，导致错误）
     * boolean hasFound 判断是否已经找到不平衡节点
     */
    private class NotBalanceNodeDetail {

        private AVLTree fatherNode;
        private AVLTree notBanlanceNode;
        private boolean hasUpdatedFather;
        private boolean hasFound;

        public NotBalanceNodeDetail() {
            hasUpdatedFather = false;
            hasFound = false;
        }

        public void init() {
            fatherNode = null;
            notBanlanceNode = null;
            hasUpdatedFather = false;
            hasFound = false;
        }


        public AVLTree getFatherNode() {
            return hasUpdatedFather ? fatherNode : null;
        }

        public void setFatherNode(AVLTree fatherNode) {
            if (hasUpdatedFather) {
                return;
            }

            this.fatherNode = fatherNode;
            hasUpdatedFather = true;
        }

        public AVLTree getNotBanlanceNode() {
            return notBanlanceNode;
        }

        public void setNotBanlanceNode(AVLTree notBanlanceNode) {
            this.hasFound = true;
            this.notBanlanceNode = notBanlanceNode;
        }

        public boolean isHasUpdatedFather() {
            return hasUpdatedFather;
        }

        public boolean isHasFound() {
            return hasFound;
        }
    }

}
